home *** CD-ROM | disk | FTP | other *** search
/ Amiga Packmags / Source, The - Issue 5 (1993)(Epsilon)[WB].zip / Source, The - Issue 5 (1993)(Epsilon)[WB].adf / Source / Vectors / VectorSpace / PointInPoly.lha / pointnpolygon.txt2 < prev    next >
Internet Message Format  |  1989-10-24  |  4KB
  1. From albanycs!leah:rsb584 Thu Mar 17 01:42:47 1988
  2. Received: by albanycs.albany.edu (5.54/4.8)
  3.     id AA17239; Wed, 16 Mar 88 22:06:21 EST
  4. Date: Wed, 16 Mar 88 22:06:13 EST
  5. From: albanycs!leah:rsb584 (Raymond S Brand)
  6. Received: by leah.Albany.EDU (5.58/1.1)
  7.     id AA27360; Wed, 16 Mar 88 22:06:13 EST
  8. Message-Id: <8803170306.AA27360@leah.Albany.EDU>
  9. To: albanycs:beowulf!rsbx
  10. Subject: polypoint.txt
  11.  
  12. >From tada@athena.mit.edu Wed Mar  2 18:22:37 1988
  13. Path: leah!itsgw!nysernic!rutgers!psuvax1!burdvax!udel!rochester!cornell!uw-beaver!mit-eddie!bloom-beacon!athena.mit.edu!tada
  14. From: tada@athena.mit.edu (Michael Zehr)
  15. Newsgroups: comp.graphics
  16. Subject: Re: point inside poly AGAIN!
  17. Summary: fast algorithm listed
  18. Message-ID: <3431@bloom-beacon.MIT.EDU>
  19. Date: 2 Mar 88 23:22:37 GMT
  20. References: <971@ut-emx.UUCP> <20533@amdcad.AMD.COM> <7626@pur-ee.UUCP> <3320@bloom-beacon.MIT.EDU> <590@naucse.UUCP>
  21. Sender: daemon@bloom-beacon.MIT.EDU
  22. Reply-To: tada@athena.mit.edu (Michael Zehr)
  23. Organization: Massachusetts Institute of Technology
  24. Lines: 70
  25.  
  26. In article <590@naucse.UUCP> rrr@naucse.UUCP (Bob Rose ) writes:
  27. >In article <3320@bloom-beacon.MIT.EDU>, tada@athena.mit.edu (Michael Zehr) writes:
  28. >> The method I use in some graphics programs requires a compare and an
  29. >> xor for each edge of the polygon, and 2 multiplies (total, not for each
  30. >> edge).
  31. >> michael j zehr
  32. >
  33. >Sounds interesting. Lets here about the algorithm, it does sound
  34. >rather specific though, like xor is not that common in (none bit mask)
  35. >graphic routines.
  36. >
  37. >                                  -bob
  38.  
  39. you got it...
  40.  
  41. (in pseudo C:)
  42.  
  43. edge[] is an array of edges
  44. an edge has two fields, end1 and end2, plus two precomputed values
  45.     to speed up the actual check: slope and intercept
  46.     slope = (end2.y - end1.y)/(end2.x - end1.x)
  47.     intercept = end2.y - slope*end2.x
  48. an "end" has two fields, x and y
  49.  
  50. (this isn't the same datastructure i'm using, so i'm paraphrasing
  51. for simplicity and readability)
  52.  
  53. flag = FALSE;
  54. for(k=0;k<num_edges;k++)
  55.     if ((x > edge[k].end1.x) ^ (x > edge[k].end2.x))
  56.         if(y < (temp = edge[k].intercept + edge[k].slope*x)
  57.         flag ^= TRUE;
  58.         else if (y==temp) 
  59.             /* point is on an edge so do whatever you want with it */;
  60.  
  61. after it's checked each edge, flag == TRUE implies it's inside,
  62. flag == FALSE implies it's outside the polygon.
  63.  
  64. the multiply only occurs when a vertical line extended from the point
  65. being tested intersects with the edge. it then computes the intersection
  66. point, and checks if the point is below the edge.  if so, it counts as
  67. an intersection.  the multiply is only executed when there is a possible
  68. intersection, which is zero, one or two times for a convex polygon. 
  69. this works as-is for concave, but doesn't guarantee only two multiplies.
  70. depending on your compiler and specific machine, it may be marginally 
  71. faster to keep track of the lowest and highest end of each edge, and
  72. put another if statement before the one that computes the actual
  73. intersection, but i haven't tried this to see
  74.  
  75. then you'd have:
  76.  
  77. if (y < edge[k].min_y) flag^= TRUE;
  78. else if (y <= edge[k].max_y) 
  79.         if (y < (temp= ....
  80.  
  81. Also, if your polygon are usually short and fat then you'd want to 
  82. change that to a horizontal line test instead of the current vertical
  83. line test.  Also, if your polygons are guaranteed convex, you could count
  84. the number of times the x tested true, and after the second one you
  85. wouldn't have to look at any more edges.
  86.  
  87. If there are special cases which aren't handled correctly, would someone
  88. please, please, PLEASE let me know.  thanks.
  89.  
  90.  
  91.  
  92.  
  93. -------
  94. michael j zehr
  95. "My opinions are my own ... as is my spelling."
  96.  
  97.  
  98.